/**
 * @author 03010570
 * @date 2020/07/10
 * describe:    LeetCode : 121 、 买卖股票的最佳时机  https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/
 */
public class LeetCode_121 {
    public static void main(String[] args) {

    }

    /**
     *  数组操作，最前面找一个最小值 ，与元素当前值比，
     *      1、当前值 - 最小值 > max ，更新max
     *      2、当前值 《 min ，更新min
     *
     *  时间复杂度：O(N)  数组的长度
     *  空间复杂度：O(1)  常数级
     * @param prices
     * @return
     */
    public int maxProfit(int[] prices) {
        int max = 0;
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < prices.length; i++) {
            int temp = prices[i] - min;
            if (temp > max) {
                max = temp;
            }
            if (prices[i] < min) {
                min = prices[i];
            }

        }
        return max;
    }

    /**
     *  动态规划（DP） ： 当前值 与 之前的每一个值比较，找出最大值
     *
     *  时间复杂度 ： O(N^2)  得循环两遍
     *  空间复杂度 ： O(1)    常数级
     * @param prices
     * @return
     */
    public int maxProfit0(int[] prices) {
        int max = 0;
        int min = Integer.MAX_VALUE;
        for(int i = 1; i<prices.length; i++){
            for(int j = 0 ; j < i ; j++){
                int temp = prices[i] - prices[j];
                if( temp > max){
                    max = temp;
                }
            }
        }
        return max;

    }
}
